'''
给你两个正整数 n 和 target 。

如果某个整数每一位上的数字相加小于或等于 target ，则认为这个整数是一个 美丽整数 。

找出并返回满足 n + x 是 美丽整数 的最小非负整数 x 。生成的输入保证总可以使 n 变成一个美丽整数。

 

示例 1：

输入：n = 16, target = 6
输出：4
解释：最初，n 是 16 ，且其每一位数字的和是 1 + 6 = 7 。在加 4 之后，n 变为 20 且每一位数字的和变成 2 + 0 = 2 。可以证明无法加上一个小于 4 的非负整数使 n 变成一个美丽整数。
示例 2：

输入：n = 467, target = 6
输出：33
解释：最初，n 是 467 ，且其每一位数字的和是 4 + 6 + 7 = 17 。在加 33 之后，n 变为 500 且每一位数字的和变成 5 + 0 + 0 = 5 。可以证明无法加上一个小于 33 的非负整数使 n 变成一个美丽整数。
示例 3：

输入：n = 1, target = 1
输出：0
解释：最初，n 是 1 ，且其每一位数字的和是 1 ，已经小于等于 target 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-addition-to-make-integer-beautiful
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
'''
class Solution(object):
    def makeIntegerBeautiful(self, n, target):
        """
        :type n: int
        :type target: int
        :rtype: int
        """
        def check(current, target):
            count = 0
            for s in str(current):
                count += int(s)

            if count <= target:
                return True
            return False

        if check(n, target):
            return 0

        str_n = str(n)
        ans = 0
        for i in range(len(str_n) - 1, -1, -1):
            base = 10 - int(str_n[i])
            if i != len(str_n) - 1:
                base -= 1
            ans += base * (10 ** (len(str_n) - i - 1))
            # check 是否满足要求
            if check(n + ans, target):
                break

        return ans

n = 1
target = 1
Solution().makeIntegerBeautiful(n,target)